package real.jindong;

import list.ListNode;


public class KReturn {

    //将给出的链表中的节点每 k 个一组翻转，返回翻转后的链表
    //如果链表中的节点数不是 k 的倍数，将最后剩下的节点保持原样
    //你不能更改节点中的值，只能更改节点本身
    private ListNode pre = null;

    public ListNode reverseKGroup (ListNode head, int k) {
        ListNode res = head;
        ListNode left = head;
        ListNode right = left;
        for(int i = 1; i < k; i++){
            right = right.next;
            if(right == null){
                return res;
            }
        }
        res = reverse(left, right);
        left = right.next;
        right = left;
        while (true){
            for(int i = 0; i < k; i++){
                right = right.next;
                if(right == null){
                    return res;
                }
            }
            reverse(left, right);
            left = right.next;
            right = left;
        }
    }

    public ListNode reverse(ListNode left, ListNode right){
        ListNode pre = left;
        ListNode nex = pre.next;
        ListNode end = right.next;
        while (!end.equals(nex)){
            ListNode next = nex.next;
            pre.next = this.pre;
            nex.next = pre;
            pre = nex;
            nex = next;
        }
        return pre;
    }
    public static void main(String[] args) {
        // 构造链表 1->2->3->4->5
        ListNode head = new ListNode(1);
        head.next = new ListNode(2);
        head.next.next = new ListNode(3);
        head.next.next.next = new ListNode(4);
        head.next.next.next.next = new ListNode(5);

        KReturn solution = new KReturn();

        // 测试用例1：k=2
        ListNode res1 = solution.reverseKGroup(head, 2);
        printList(res1); // 期望输出：2->1->4->3->5

        // 测试用例2：k=3
        ListNode head2 = new ListNode(1);
        head2.next = new ListNode(2);
        head2.next.next = new ListNode(3);
        head2.next.next.next = new ListNode(4);
        head2.next.next.next.next = new ListNode(5);
        ListNode res2 = solution.reverseKGroup(head2, 3);
        printList(res2); // 期望输出：3->2->1->4->5

        // 测试用例3：k=1
        ListNode head3 = new ListNode(1);
        head3.next = new ListNode(2);
        head3.next.next = new ListNode(3);
        ListNode res3 = solution.reverseKGroup(head3, 1);
        printList(res3); // 期望输出：1->2->3
    }

    // 辅助方法：打印链表
    public static void printList(ListNode node) {
        while (node != null) {
            System.out.print(node.val);
            if (node.next != null) {
                System.out.print("->");
            }
            node = node.next;
        }
        System.out.println();
    }

}
